#include <iostream>
#include <cstring>
using namespace std;
//记录搜索的递归计算
int fib(int *M,int j)
{
    if(M[j]==-1)    //如果还没有被计算
        M[j]=fib(M,j-1)+fib(M,j-2);   //进行计算
    return M[j];    //返回结果
}
//自顶向下求解
int top_down(int n)
{
    int *M=new int[n+1];    //建立元素为n+1的数组
    memset(M,-1,sizeof(int)*(n+1)); //填充为-1
    M[0]=0;M[1]=1;  //设置初始值
    int res=fib(M,n);    //计算结果
    delete[] M; //释放空间
    return res;
}
//自底向上求解
int bottom_up(int n)
{
    int *M=new int[n+1];    //建立元素为n+1的数组
    memset(M,-1,sizeof(int)*(n+1)); //填充为-1
    M[0]=0;M[1]=1;  //设置初始值
    for(int i=2;i<=n;i++)
    {
        M[i]=M[i-1]+M[i-2]; //计算数目
    }
    int res=M[n];   //获取结果
    delete[] M; //释放空间
    return res;
}
int main()
{
    int num=10;
    cout<<"top_down fib "<<num<<" is "<<top_down(num)<<endl;
    cout<<"bottom_up fib "<<num<<" is "<<bottom_up(num)<<endl;
    return 0;
}
